package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/wildcard-matching/description/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/9/8 10:13
 * @since JDK17
 */

public class Solution96 {
    char []s, p;
    int [][] dp;
    int dfs(int i, int j) {
        if (i == 0 && j == 0) {
            return 1;
        }
        if (i == 0) {
            return dp[i][j] = p[j - 1] == '*' ? dfs(i, j - 1) : 0;
        }
        if (j == 0) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }

        if (s[i - 1] != p[j - 1]) {
            if (p[j - 1] == '?') {
                return dp[i][j] = dfs(i - 1, j - 1);
            } else if (p[j - 1] == '*'){
                return dp[i][j] = Math.max(dfs(i - 1, j), dfs(i, j - 1));
            }
        } else {
            return dp[i][j] = dfs(i - 1, j - 1);
        }
        return 0;
    }
    public boolean isMatch(String s, String p) {
        this.s = s.toCharArray();
        this.p = p.toCharArray();
        dp = new int[s.length() + 1][p.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(s.length(), p.length()) == 1 ? true : false;
    }
}
